import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {

    }

    public int singleNumber1(int[] nums) {
        /**
         * 只出现一次的数字Ⅱ
         * 解法一：
         *  使用哈希表*/
        // 1 准备HashMap，结构为 值：次数
        Map<Integer, Integer> map = new HashMap<>();

        // 2 遍历计数
        for(int e: nums) {
            map.put(e, map.getOrDefault(e, 0) + 1);
        }

        // 3 查找
        for(int e: nums) {
            if(map.get(e) == 1) {
                return e;
            }
        }
        return -1;
    }

    public int singleNumber(int[] nums) {
        /**
         * 只出现一次的数字Ⅱ
         * 解法二：
         *  使用对比特位进行计算，原理第一次听说
         * 原理：
         *  已知除了一个元素出现一次外，其余所有元素均出现了三次
         *  故若是我们按位将每个bit位进行相加处理，则可能会出现4中情况
         *      1,3n * 1 + 0 = 3n
         *      2,3n * 1 + 1 = 3n + 1
         *      3,3n * 0 + 0 = 0
         *      4,3n * 0 + 1 = 1
         *  一：若是为0，那么剩余的就是我们仅出现一次的数字
         *  二：若是为1，由于必定出现3次，故我们模3后，就是我们仅出现一次的数字
         *  即可解*/
        // 1 创建返回值
        int ret = 0;

        // 2 遍历
        for(int i = 0; i < 32; i++) {
            // -累加所有元素i位比特位之和
            int sum = 0;
            for(int e: nums) {
                sum += ((e>>i) & 1);
            }
            sum %= 3;
            // -设置返回值bit位
            if(sum == 1) {
                ret |= (1<<i);
            }
        }

        // 3 返回值
        return ret;
    }
}
